package ljl.alg.wangzheng_camp.round1.slidingwindow;

import java.util.LinkedList;

/**
 * 这个题也刷了五六遍了，可是不能说难！
 * */
public class _offer59_1_sliding_window_max {
    
    /*
    * 这个是队列里存下标，其实也可以存数据
    * */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i])
                q.pollLast();
            q.offer(i);
        }
        int n = nums.length;
        int[] res = new int[n - k + 1];
        res[0] = nums[q.peekFirst()];
        for (int i = k; i < n; i++) {
            if (q.peekFirst() == i - k) {
                q.pollFirst();
            }
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i])
                q.pollLast();
            q.offer(i);
            res[i - k + 1] = nums[q.peekFirst()];
        }
        return res;
    }
    
    /*
    * 来个队列里存数据的，大同小异
    * */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!q.isEmpty() && q.peekLast() < nums[i])
                q.pollLast();
            q.offer(nums[i]);
        }
        int n = nums.length;
        int[] res = new int[n - k + 1];
        res[0] = q.peekFirst();
        for (int i = k; i < n; i++) {
            if (q.peekFirst() == nums[i - k]) {
                q.pollFirst();
            }
            while (!q.isEmpty() && q.peekLast() < nums[i])
                q.pollLast();
            q.offer(nums[i]);
            res[i - k + 1] = q.peekFirst();
        }
        return res;
    }
    
}
